1.9 Ejemplo de lista abierta ordenada en C:  

Supongamos que queremos construir una lista para almacenar números enteros, pero de modo que siempre esté ordenada de menor a mayor. Para hacer la prueba añadiremos los valores 20, 10, 40, 30. De este modo tendremos todos los casos posibles. Al comenzar, el primer elemento se introducirá en una lista vacía, el segundo se insertará en la primera posición, el tercero en la última, y el último en una posición intermedia.

Insertar un elemento en una lista vacía es equivalente a insertarlo en la primera posición. De modo que no incluiremos una función para asignar un elemento en una lista vacía, y haremos que la función para insertar en la primera posición nos sirva para ese caso también.

Algoritmo de inserción:

1. El primer paso es crear un nodo para el dato que vamos a insertar.
2. Si Lista es NULL, o el valor del primer elemento de la lista es mayor que el del nuevo, insertaremos el nuevo nodo en la primera posición de la lista.
3. En caso contrario, buscaremos el lugar adecuado para la inserción, tenemos un puntero "anterior". Lo inicializamos con el valor de Lista, y avanzaremos mientras anterior->siguiente no sea NULL y el dato que contiene anterior->siguiente sea menor o igual que el dato que queremos insertar.
4. Ahora ya tenemos anterior señalando al nodo adecuado, así que insertamos el nuevo nodo a continuación de él.

void Insertar(Lista *lista, int v) {
   pNodo nuevo, anterior;
 
   /* Crear un nodo nuevo */
   nuevo = (pNodo)malloc(sizeof(tipoNodo));
   nuevo->valor = v;
   
   /* Si la lista está vacía */
   if(ListaVacia(*lista) || (*lista)->valor > v) {
      /* Añadimos la lista a continuación del nuevo nodo */
      nuevo->siguiente = *lista; 
      /* Ahora, el comienzo de nuestra lista es en nuevo nodo */
      *lista = nuevo;
   }
   else {
      /* Buscar el nodo de valor menor a v */
      anterior = *lista;
      /* Avanzamos hasta el último elemento o hasta que el siguiente tenga 
         un valor mayor que v */
      while(anterior->siguiente && anterior->siguiente->valor <= v) 
         anterior = anterior->siguiente;
      /* Insertamos el nuevo nodo después del nodo anterior */
      nuevo->siguiente = anterior->siguiente;
      anterior->siguiente = nuevo;
   }
}

Algoritmo para borrar un elemento:

Después probaremos la función para buscar y borrar, borraremos los elementos 10, 15, 45, 30 y 40, así probaremos los casos de borrar el primero, el último y un caso intermedio o dos nodos que no existan.

Recordemos que para eliminar un nodo necesitamos disponer de un puntero al nodo anterior.

1. Lo primero será localizar el nodo a eliminar, si es que existe. Pero sin perder el puntero al nodo anterior. Partiremos del nodo primero, y del valor NULL para anterior. Y avanzaremos mientras nodo no sea NULL o mientras que el valor almacenado en nodo sea menor que el que buscamos.
2. Ahora pueden darse tres casos:
3. Que el nodo sea NULL, esto indica que todos los valores almacenados en la lista son menores que el que buscamos y el nodo que buscamos no existe. Retornaremos sin borrar nada.
4. Que el valor almacenado en nodo sea mayor que el que buscamos, en ese caso también retornaremos sin borrar nada, ya que esto indica que el nodo que buscamos no existe.
5. Que el valor almacenado en el nodo sea igual al que buscamos.
6. De nuevo existen dos casos:
7. Que anterior sea NULL. Esto indicaría que el nodo que queremos borrar es el primero, así que modificamos el valor de Lista para que apunte al nodo siguiente al que queremos borrar.
8. Que anterior no sea NULL, el nodo no es el primero, así que asignamos a anterior->siguiente la dirección de nodo->siguiente.
9. Después de 7 u 8, liberamos la memoria de nodo.

void Borrar(Lista *lista, int v) {
   pNodo anterior, nodo;
   
   nodo = *lista;
   anterior = NULL;
   while(nodo && nodo->valor < v) {
      anterior = nodo; 
      nodo = nodo->siguiente;
   }
   if(!nodo || nodo->valor != v) return;
   else { /* Borrar el nodo */
      if(!anterior) /* Primer elemento */
         *lista = nodo->siguiente;
      else  /* un elemento cualquiera */
         anterior->siguiente = nodo->siguiente;
      free(nodo);
   }   
}

Código del ejemplo completo:

#include <stdlib.h>
#include <stdio.h>
 
typedef struct _nodo {
   int valor;
   struct _nodo *siguiente;
} tipoNodo;
 

typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
 
/* Funciones con listas: */
void Insertar(Lista *l, int v);
void Borrar(Lista *l, int v);
 
int ListaVacia(Lista l);
 
void BorrarLista(Lista *);
void MostrarLista(Lista l);
 
int main() {
   Lista lista = NULL;
   pNodo p;
 
   Insertar(&lista, 20);
   Insertar(&lista, 10);
   Insertar(&lista, 40);
   Insertar(&lista, 30);

   MostrarLista(lista);

   Borrar(&lista, 10);
   Borrar(&lista, 15);
   Borrar(&lista, 45);
   Borrar(&lista, 30);
   Borrar(&lista, 40);

   MostrarLista(lista);
   
   BorrarLista(&lista);

   getchar();
   return 0;
}

void Insertar(Lista *lista, int v) {
   pNodo nuevo, anterior;
 
   /* Crear un nodo nuevo */
   nuevo = (pNodo)malloc(sizeof(tipoNodo));
   nuevo->valor = v;
   
   /* Si la lista está vacía */
   if(ListaVacia(*lista) || (*lista)->valor > v) {
      /* Añadimos la lista a continuación del nuevo nodo */
      nuevo->siguiente = *lista; 
      /* Ahora, el comienzo de nuestra lista es en nuevo nodo */
      *lista = nuevo;
   }
   else {
      /* Buscar el nodo de valor menor a v */
      anterior = *lista;
      /* Avanzamos hasta el último elemento o hasta que el siguiente tenga 
         un valor mayor que v */
      while(anterior->siguiente && anterior->siguiente->valor <= v) 
         anterior = anterior->siguiente;
      /* Insertamos el nuevo nodo después del nodo anterior */
      nuevo->siguiente = anterior->siguiente;
      anterior->siguiente = nuevo;
   }
}

void Borrar(Lista *lista, int v) {
   pNodo anterior, nodo;
   
   nodo = *lista;
   anterior = NULL;
   while(nodo && nodo->valor < v) {
      anterior = nodo; 
      nodo = nodo->siguiente;
   }
   if(!nodo || nodo->valor != v) return;
   else { /* Borrar el nodo */
      if(!anterior) /* Primer elemento */
         *lista = nodo->siguiente;
      else  /* un elemento cualquiera */
         anterior->siguiente = nodo->siguiente;
      free(nodo);
   }   
}

int ListaVacia(Lista lista) {
   return (lista == NULL);
}

void BorrarLista(Lista *lista) {
   pNodo nodo;

   while(*lista) {
      nodo = *lista;
      *lista = nodo->siguiente;
      free(nodo);
   }
}

void MostrarLista(Lista lista) {
   pNodo nodo = lista;

   if(ListaVacia(lista)) printf("Lista vacía\n");
   else {
      while(nodo) {
         printf("%d -> ", nodo->valor);
         nodo = nodo->siguiente;
     }
     printf("\n");
   }
}

Fichero con el código fuente.